UVa/116 - Undirectional TSP/116.cpp

   1  #include <iostream>
   2  #include <vector>
   3
   4 using namespace std;
   5
   6 int main(){
   7   int rows, cols;
   8   while(cin >> rows >> cols){
   9     //g = matriz de entrada
  10     long long g[rows][cols];
  11     //dp[i][j] = minimo peso para llegar a la casilla (i,j)
  12     //empezando en cualquiera de la última columna
  13     long long dp[rows][cols];
  14     //p[i][j] = Fila en la que estuve antes de llegar a la casilla
  15     //(i,j), pero recorriendo la matriz de derecha a izquierda
  16     int p[rows][cols];
  17     for (int i=0; i<rows; ++i){
  18       for (int j=0; j<cols-1; ++j){
  19         cin >> g[i][j];
  20         dp[i][j] = LLONG_MAX;
  21         p[i][j] = -1;
  22       }
  23       cin >> g[i][cols-1];
  24       dp[i][cols-1] = g[i][cols-1];
  25       p[i][cols-1] = -1;
  26     }
  27
  28     for (int j=cols-2; j>=0; --j){
  29       for (int i=0; i<rows; ++i){
  30         int previousRows[] = {(i+rows-1)%rows, i, (i+1)%rows };
  31         sort(previousRows, previousRows + 3);
  32         for (int k=0; k<3; ++k){
  33           if (dp[previousRows[k]][j+1] < dp[i][j]){
  34             dp[i][j] = dp[previousRows[k]][j+1];
  35             p[i][j] = previousRows[k];
  36           }
  37         }
  38         dp[i][j] += g[i][j];
  39       }
  40     }
  41
  42     long long minWeight = LLONG_MAX, firstRow = -1;
  43     for (int i=0; i<rows; ++i){
  44       if (dp[i][0] < minWeight){
  45         firstRow = i;
  46         minWeight = dp[i][0];
  47       }
  48     }
  49
  50     vector<int> path;
  51     int i = firstRow;
  52     int j = 0;
  53     while (j < cols-1){
  54       path.push_back(p[i][j]);
  55       i = p[i][j];
  56       ++j;
  57     }
  58
  59     cout << firstRow + 1;
  60     for (int i=0; i<path.size(); ++i){
  61       cout << " " << path[i] + 1;
  62     }
  63     cout << endl;
  64     cout << minWeight << endl;
  65   }
  66   return 0;
  67 }